昨天介紹完了堆疊，今天要來講講堆疊的重要應用吧！

infix, postfix, prefix expression

這是三種式子的表達方式，我們來好好介紹他：
若今天的運算式有兩個運算元（operand），一個運算子（operator）：

1. 中序表達式（Infix）：operand 1 | operator | operand 2
   也就是我們人最習慣的表達方式（e.g. A + B, A - B, A / B）
   雖然我們人類很容易理解，但會造成compiler在編譯時的麻煩，因為要考慮 operator 的優先權及結合問題，可能會導致需要來回 scan 才能求出解答。
   例如：A + B * C => compiler掃到 "A" 和 "+" 後，卻發現 B * C 之優先權較高，因此只能先做 B * C，再重新 scan A 來加入。
2. 前序表達式（prefix）：operator | operand 1 | operand 2
   compiler只需要由右至左 scan 一次即可得出解答，但需要 2 個 stack 支援（e.g. + A B, - A B, / A B）
3. 後序表達式（postfix）：operand 1| operand 2 | operator
   compiler只需要由左至右 scan 一次即可得出解答，只需要 1 個 stack 支援（e.g. A B +, A B -, A B /）

因此基本上 compiler 使用 postfix expression 的效能較佳。流程如下：
infix expression => postfix expression => postfix evaluation => answer
其中會經過一次中序轉後序的演算法，以及後序求值的演算法。馬上來看看

infix to postfix transformation

基本原則：如果是運算元則直接輸出，如果是 operator 則與堆疊頂端之元素比較優先權（precedence），若堆疊外運算子優先權較高（>），則 push 入堆疊，否則（<=），則持續 pop 元素，直到堆疊外運算子之優先權 > 堆疊頂端元素之優先權。
至於為甚麼要怎麼做，可以這麼想：優先權較高之元素要先做，因此就是要 push 堆疊頂端，因為 Last-In First-Out
如果碰到括號 "("、")"，將左括號直接 push 進入堆疊，且左括號在堆疊內的優先權最低，因此除非遇到右括號，不然不會離開堆疊。若碰到右括號，則 pop 左括號以上的所有元素並輸出，再將左右括號皆捨棄。因為後序表達式不需要括號來表示先後順序。
若表達式已經掃描完畢，堆疊內還有元素，則陸續 pop 出來 output。
來練習一題：
Infix expression: A * B - C / (D - E)

因此答案就是：A B * C D E - / -

postfix evaluation

現在我們已經會將 infix expression 轉換成 postfix expression 了
現在要來計算這個後序式子的值，跟剛剛的轉換不同：
基本原則：遇到 operand 則 push 進入堆疊，遇到 operator 則 pop 該 operator 所需之 operand 進行運算，計算完後再將值 push 回堆疊。
scan 結束後在堆疊中的數字，就是答案。
馬上再來看一題：
若 A = 1, B = 2, C = 3, D = 4, E = 5 則 A B * C D E - / - 值為何？

答案就是：5

堆疊的其他應用

堆疊還有很多應用，例如：判斷文法是否正確（Compiler Parsing, palindrome）、反序輸出（reverse ordering）、甚至在接下來的 Tree、Graph 都會用到、OS 中也使用 Stack 來保存副程式呼叫及遞回呼叫的 Activation code，雖然很基本，但是相當的實用！

明天要來說 Queue